package chapter_03.list_stack_queue;

import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * @ClassName MySingleLinkedList
 * @Discription 单链表
 **/
public class MySingleLinkedList<T> implements Iterable<T> {
    private int theSize;
    //自构造以来对链表的所做改变的次数
    private int modCount = 0;
    private Node<T> nextMarker;

    public MySingleLinkedList() {
        clear();
    }

    public void clear() {
        nextMarker = new Node<>(null, null);
        theSize = 0;
        modCount++;
    }

    public T get(int idx) {
        return this.getBeforeNode(idx, theSize - 1).next.getData();
    }

    public T update(int idx, T value) {
        Node<T> oldNode = this.getNode(idx);
        T old = oldNode.getData();

        oldNode.setData(value);
        modCount++;
        return old;
    }

    private Node<T> getNode(int idx) {
        return this.getBeforeNode(idx, theSize - 1).next;
    }

    private Node<T> getBeforeNode(int idx, int upper) {
        if (idx < 0 || idx > upper) {
            throw new IndexOutOfBoundsException();
        }

        Node<T> pointer = nextMarker;
        int tag = 0;
        while (true) {
            if (idx == tag) {
                return pointer;
            }

            pointer = pointer.next;
            tag++;
        }
    }

    public void add(T value) {
        if (theSize == 0) {
            add(0, value);
        } else {
            add(theSize, value);
        }
    }

    public void add(int idx, T value) {
        Node<T> beforeNode = this.getBeforeNode(idx, theSize);
        Node<T> tNode = new Node<>(value, beforeNode.next);
        beforeNode.next = tNode;
        theSize++;
        modCount++;
    }

    public T remove(int idx) {
        modCount++;
        theSize--;
        return remove(getNode(idx));
    }

    private T remove(Node<T> node) {
        Node tmp = nextMarker;
        while (true) {
            Node<T> before = tmp;
            Node<T> current = tmp.next;
            if (current == null) {
                break;
            } else if (node == current) {
                before.next = current.next;
                return node.getData();
            }

            tmp = tmp.next;
        }

        return null;
    }

    public int getSize() {
        return theSize;

    }
    @Override
    public Iterator<T> iterator() {
        return new SingleLinkedIterator();
    }

    private class SingleLinkedIterator implements Iterator<T> {
        private Node<T> current = nextMarker.next;
        private int expectedModCount = modCount;
        private boolean okToRemove = false;

        @Override
        public boolean hasNext() {
            return current != null;
        }

        @Override
        public T next() {
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }

            if (!hasNext()) {
                throw new NoSuchElementException();
            }


            T nextItem = current.data;
            current = current.next;
            okToRemove = true;
            return nextItem;
        }

        @Override
        public void remove() {
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }

            if (!okToRemove) {
                throw new IllegalStateException();
            }

            MySingleLinkedList.this.remove(current);
            expectedModCount++;
            okToRemove = false;
        }
    }

    private static class Node<T> {

        public T data;
        public Node<T> next;

        public T getData() {
            return data;
        }

        public Node<T> setData(T data) {
            this.data = data;
            return this;
        }

        public Node<T> getNext() {
            return next;
        }

        public Node<T> setNext(Node<T> next) {
            this.next = next;
            return this;
        }

        public Node(T d, Node<T> n) {
            data = d;
            next = n;
        }

    }
}
